class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        n++;
        vector<vector<vector<int>>> vv(n + 1);

        vector<int> a(n + 1, -1);
        for (auto& e : times) {
            vv[e[0]].push_back({e[1], e[2]});
        }
        auto dfs = [&](auto& dfs, int pos, int time) {
            if (a[pos] == -1 || a[pos] > time) {
                a[pos] = time;
            } else {
                return;
            }
            for (auto& e : vv[pos]) {
                dfs(dfs, e[0], time + e[1]);
            }
        };
        dfs(dfs, k, 0);
        int ans = 0;
        for (int i = 1; i < n; i++) {
            // cout << i << ' ' << a[i] << endl;
            ans = max(ans, a[i]);
            if (a[i] == -1)
                return -1;
        }
        return ans;
    }
};